package leetCode.sample;

import org.junit.Test;

import java.util.Arrays;

public class SearchRangeSolution {

    @Test
    public void test() {

        System.out.println(Arrays.toString(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 8)));
        System.out.println(Arrays.toString(searchRange(new int[]{5, 7, 7, 8, 8, 10}, 6)));
        System.out.println(Arrays.toString(searchRange(new int[]{1}, 1)));
        System.out.println(Arrays.toString(searchRange(new int[]{1, 4}, 4)));
    }


    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        if (nums.length == 0) {
            return result;
        }
        if (nums.length == 1 && nums[0] == target) {
            return new int[]{0, 0};
        }
        //int index = search(nums, 0, nums.length - 1, target);
        int index = binarySearch(nums,  target);
        if (index >= 0) {
            int left = index;
            while (left >= 0 && nums[left] == target) {
                result[0] = left;
                left--;
            }
            int right = index;
            while (right < nums.length && nums[right] == target) {
                result[1] = right;
                right++;
            }
        }
        return result;
    }

    private int search(int[] nums, int left, int right, int target) {
        int middle = (left + right) / 2;
        if (nums[middle] == target) {
            return middle;
        }
        if (right == left) {
            return -1;
        }
        if (nums[middle] < target) {
            return search(nums, middle + 1, right, target);
        }
        if (nums[middle] > target) {
            return search(nums, left, middle, target);
        }
        return -1;
    }


    private int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while(left <= right) {
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }


}
